#include "BinaryTree.h"
#include <queue>

BinaryTree::BinaryTree()
{
  m_root = NULL;
  cout << "BinaryTree constructor." << endl;
}

BinaryTree::~BinaryTree()
{
  destroyTree(&m_root);
  cout << "~BinaryTree" << endl;
}

int32_t BinaryTree::build()
{
  return create(&m_root);
}

int32_t BinaryTree::create(treeNode** node)
{
  if (node == NULL) {
    cout << "param can't NULL." << endl;
    return -1;
  }

  char v = 0;
  cout << "input node value, "
       << "input '$' to complete create this node." << endl;
  cin >> v;

  if (v == '$') {
    *node = NULL;
    return 0;
  }

  *node = (treeNode*)malloc(sizeof(treeNode));
  if (*node == NULL) {
    cout << "[create] out of memory!" << endl;
    return -2;
  }

  (*node)->value = v;
  cout << "create one node ok, value is " << v << endl;
  cout << "ready to create node(" << v << ")'s left child tree." << endl; 
  if (create(&(*node)->lChild)) {
    cout << "create left child tree fail!" << endl;
    return -3;
  }

  cout << "ready to create node(" << v << ")'s right child tree." << endl; 
  if (create(&(*node)->rChild)) {
    cout << "create right child tree fail!" << endl;
    return -3;
  }

  return 0;
}

int32_t BinaryTree::destroyTree(treeNode** node)
{
  if (*node != NULL) {
    destroyTree(&(*node)->lChild);
    destroyTree(&(*node)->rChild);
    free(*node);
    *node = NULL;
    cout << "free memory ok." << endl;
  }

  return 0;
}

int32_t BinaryTree::firstVisitRoot()
{
  if (m_root == NULL) {
    cout << "[firstVisitRoot] it is a empty tree!" << endl;
    return 0;
  }

  return firstVisitRoot(m_root);
}

int32_t BinaryTree::firstVisitRoot(treeNode* node)
{
  if (node == NULL) {
    cout << "[firstVisitRoot] this node is NULL." << endl;
    return 0;
  }

  cout << "[firstVisitRoot] >>>>>> this node is " << node->value << endl;
  //cout << "[firstVisitRoot] ready to visit node(" << node->value << ")'s lChild" << endl;
  firstVisitRoot(node->lChild);
  //cout << "[firstVisitRoot] ready to visit node(" << node->value << ")'s rChild" << endl;
  return firstVisitRoot(node->rChild);
}

int32_t BinaryTree::middleVisitRoot()
{
  if (m_root == NULL) {
    cout << "[middleVisitRoot] it is a empty tree!" << endl;
    return 0;
  }

  return middleVisitRoot(m_root);
}

int32_t BinaryTree::middleVisitRoot(treeNode* node)
{
  if (node == NULL) {
    cout << "[middleVisitRoot] this node is NULL." << endl;
    return 0;
  }

  //cout << "[middleVisitRoot] ready to visit node(" << node->value << ")'s lChild" << endl;
  middleVisitRoot(node->lChild);

  cout << "[middleVisitRoot] >>>>>> this node is " << node->value << endl;

  //cout << "[middleVisitRoot] ready to visit node(" << node->value << ")'s rChild" << endl;
  return middleVisitRoot(node->rChild);
}

int32_t BinaryTree::lastVisitRoot()
{
  if (m_root == NULL) {
    cout << "[lastVisitRoot] it is a empty tree!" << endl;
    return 0;
  }

  return lastVisitRoot(m_root);
}

int32_t BinaryTree::lastVisitRoot(treeNode* node)
{
  if (node == NULL) {
    cout << "[lastVisitRoot] this node is NULL." << endl;
    return 0;
  }

  //cout << "[lastVisitRoot] ready to visit node(" << node->value << ")'s lChild" << endl;
  lastVisitRoot(node->lChild);

  //cout << "[lastVisitRoot] ready to visit node(" << node->value << ")'s rChild" << endl;
  lastVisitRoot(node->rChild);

  cout << "[lastVisitRoot] >>>>>> this node is " << node->value << endl;
  return 0;
}

int32_t BinaryTree::levelVisit()
{
  if (m_root == NULL) {
    cout << "[levelVisit] it is a empty tree!" << endl;
    return 0;
  }

  queue<treeNode*> pendingNode;
  pendingNode.push(m_root);

  while (!pendingNode.empty()) {
    treeNode* node = pendingNode.front();
    pendingNode.pop();
    cout << "[levelVisit] >>>>>> this node is " << node->value << endl;
    if (node->lChild != NULL) pendingNode.push(node->lChild);
    if (node->rChild != NULL) pendingNode.push(node->rChild);
  }

  return 0;
}
